/**
 * 215. 数组中的第K个最大元素
 * https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
 */

// /**
//  * @param {number[]} nums
//  * @param {number} begin
//  * @param {number} end
//  * @param {number} target
//  * @return {number}
//  */
// function quickSelect(nums, begin, end, target) {
//   const base = nums[begin];
//   let left = begin;
//   let right = end;
//   while (left < right) {
//     while (left < right && nums[right] >= base) {
//       right -= 1;
//     }
//     while (left < right && nums[left] <= base) {
//       left += 1;
//     }
//     const temp = nums[left];
//     nums[left] = nums[right];
//     nums[right] = temp;
//   }
//   if (left === target) {
//     return base;
//   }
//   nums[begin] = nums[left];
//   nums[left] = base;
//   if (left > target) {
//     return quickSelect(nums, begin, left - 1, target);
//   }
//   return quickSelect(nums, left + 1, end, target);
// }
//
// /**
//  * 剪枝快排
//  * @param {number[]} nums
//  * @param {number} k
//  * @return {number}
//  */
// function findKthLargest(nums, k) {
//   const { length } = nums;
//   return quickSelect(nums, 0, length - 1, length - k);
// }

/**
 * @param {number[]} nums
 * @param {number} a
 * @param {number} b
 */
function swap(nums, a, b) {
  const temp = nums[a];
  nums[a] = nums[b];
  nums[b] = temp;
}

/**
 * @param {number} index
 * @param {number[]} nums
 * @param {number} length
 */
function resolveChild(index, nums, length) {
  if (index >= length) {
    return;
  }
  const leftIndex = index * 2 + 1;
  if (leftIndex >= length) {
    return;
  }
  const rightIndex = leftIndex + 1;
  const value = nums[index];
  const left = nums[leftIndex];
  const right = rightIndex >= length ? -Infinity : nums[rightIndex];
  if (value >= left && value >= right) {
    return;
  }
  if (left >= right) {
    swap(nums, index, leftIndex);
    resolveChild(leftIndex, nums, length);
  } else {
    swap(nums, index, rightIndex);
    resolveChild(rightIndex, nums, length);
  }
}

/**
 * @param {number[]} nums
 * @param {number} length
 */
function completeTree(nums, length) {
  for (let i = Math.floor(length / 2 - 1); i >= 0; i -= 1) {
    resolveChild(i, nums, length);
  }
}

/**
 * 剪枝堆排
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
function findKthLargest(nums, k) {
  const end = nums.length - k;
  for (let l = nums.length; l > end; l -= 1) {
    completeTree(nums, l);
    swap(nums, 0, l - 1);
  }
  return nums[end];
}

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2) === 5);
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4) === 4);
